package 题目集.单调栈or队列.单调队列;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 接取落水的最小花盆
 * 老板需要你帮忙浇花。给出 N 滴水的坐标，y 表示水滴的高度，x 表示它下落到 x 轴的位置
 * 每滴水以每秒1个单位长度的速度下落。你需要把花盆放在 x 轴上的某个位置
 * 使得从被花盆接着的第 1 滴水开始，到被花盆接着的最后 1 滴水结束，之间的时间差至少为 D
 * 我们认为，只要水滴落到 x 轴上，与花盆的边沿对齐，就认为被接住
 * 给出 N 滴水的坐标和 D 的大小，请算出最小的花盆的宽度 W
 * 测试链接 : https://www.luogu.com.cn/problem/P2698
 */
public class 接取落水的最小花盆 {

    static int[][] arr;
    static int d;
    static int n;

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n = sc.nextInt();
        d = sc.nextInt();
        arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);
        int fun = fun();
        System.out.println(fun);
    }

    public static int fun() {
        int[] maxQueue = new int[n];
        int[] minQueue = new int[n];
        int maxHead = 0, maxTail = 0;
        int minHead = 0, minTail = 0;

        int w = Integer.MAX_VALUE;

        for (int i = 0, j = 0; j < arr.length; j++) {
            while (maxHead != maxTail && arr[j][1] > arr[maxQueue[maxTail - 1]][1]) {
                maxTail--;
            }
            maxQueue[maxTail] = j;
            maxTail = (maxTail + 1) % n;

            while (minHead != minTail && arr[j][1] < arr[minQueue[minTail - 1]][1]) {
                minTail--;
            }
            minQueue[minTail] = j;
            minTail = (minTail + 1) % n;

            while (arr[maxQueue[maxHead]][1] - arr[minQueue[minHead]][1] >= d) {
                w = Math.min(w, arr[j][0] - arr[i][0]);
                if (maxQueue[maxHead] == i) {
                    maxHead = (maxHead + 1) % n;
                }
                if (minQueue[minHead] == i) {
                    minHead = (minHead + 1) % n;
                }
                i++;
            }
        }
        return w==Integer.MAX_VALUE?-1:w;
    }
}
